/*
 * @lc app=leetcode id=456 lang=cpp
 *
 * [456] 132 Pattern
 */

// @lc code=start
class Solution {
public:
        bool find132pattern(vector<int>& nums) {
            if (nums.size() < 2) {
            return false;
        }
        map<int, int> table;
        for (int i = 2; i < nums.size(); ++i) {
            table[nums[i]]++;
        }
        int ms = nums[0];
        for (int i = 1; i < nums.size() - 1; ++i) {
            ms = std::min(nums[i - 1], ms);
            if (nums[i] > nums[i + 1] && nums[i] > ms) {
            auto iter = table.upper_bound(ms);
            if (iter == table.end()) {
                continue;
            }
            if (iter->first < nums[i]) {
                return true;
            }
            }
            if (i + 1 >= 2) {
            table[nums[i + 1]]--;
            if (table[nums[i + 1]] == 0) {
                table.erase(nums[i + 1]);
            }
            }
        }

  return false;

    }
};
// @lc code=end

